﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Xml;
using System.Xml.Serialization;
using System.IO;
using System.Threading;

namespace PathFinder
{
    [Serializable()]
    public class Graph
    {
        #region class definitions
        private List<GraphLine> output;
        public List<GraphLine> Output { get { return output; } }
        [XmlIgnore]
        public bool aborted = false;
        private List<Thread> threadList;
        public int GetThreadCount { get { return threadList.Count; } }
        public List<GraphPoint> GraphPoints;
        public List<GraphLine> GraphLines;
        public GraphPoint start;
        public GraphPoint end;
        [XmlIgnore]
        public List<GraphLine> WalkThroughGraphLines;
        [XmlIgnore]
        public List<GraphPoint> WalkThroughGraphPoints;
        [XmlIgnore]
        public List<GraphLine> WalkThroughGraphLinesBanlist;
        private List<List<GraphLine>> usedPairs = new List<List<GraphLine>>();
        private Stack<GraphPoint> S;
        private Stack<GraphLine> S2;
        [XmlIgnore]
        public int PercentDone = 0;
        public Graph()
        {
            GraphLines = new List<GraphLine>();
            GraphPoints = new List<GraphPoint>();
        }

        public Graph(Graphics G)
        {
            GraphLines = new List<GraphLine>();
            GraphPoints = new List<GraphPoint>();
        }

        #endregion

        #region subclasses

        public class PerfectMatchingThread
        {
            static Graph Gr;
            List<GraphPoint> Odds;
            List<GraphLine> Pairs;
            List<double> PairsDistances;
            public List<GraphLine> val = new List<GraphLine>();
            bool IsRoot;
            public Thread t;
            int complete;

            public PerfectMatchingThread(List<GraphPoint> odds, List<GraphLine> pairs, List<double> pairsDistances, Graph gr = null)
            {
                Odds = odds; 
                Pairs = pairs;
                PairsDistances = pairsDistances;
                if (gr != null)
                {
                    Gr = gr;
                    IsRoot = true;
                }
                else IsRoot = false;
                if(!Gr.aborted)
                    t = new Thread(new ThreadStart(perfectMatching));
            }

            private void perfectMatching()
            {
                if (Gr.aborted)
                    return;
                complete = 0;
                List<List<GraphLine>> values = new List<List<GraphLine>>();
                List<GraphPoint> oddsDown = new List<GraphPoint>();
                List<PerfectMatchingThread> threads = new List<PerfectMatchingThread>();
                GraphPoint a;
                GraphPoint b;
                GraphLine current = null;
                a = Odds[0];

                for (int j = 1; j < Odds.Count; j++)
                {
                    b = Odds[j];
                    current = new GraphLine(a, b);
                    oddsDown.Clear();
                    foreach (GraphPoint pt in Odds)
                    {
                        if (pt != a && pt != b)
                            oddsDown.Add(pt);
                    }
                    if (Gr.aborted)
                        return;
                    if (oddsDown.Count >= 10 && IsRoot)
                    {
                        PerfectMatchingThread perf = new PerfectMatchingThread(oddsDown, Pairs, PairsDistances);
                        oddsDown = new List<GraphPoint>();
                        threads.Add(perf);
                        val.Add(current);
                    }
                    else if (!IsRoot || threads.Count == 0)
                        if (oddsDown.Count > 1)
                        {
                            List<GraphLine> l = Gr.perfectMatching(oddsDown, Pairs, PairsDistances);
                            l.Add(current);
                            values.Add(l);
                        }
                        else
                        {
                            val.Add(current);
                        }
                }
                complete = 10;
                foreach (PerfectMatchingThread th in threads)
                {
                    try
                    {
                        if (Gr.aborted)
                            return;
                        th.t.Start();
                        Gr.threadList.Add(th.t);
                    }
                    catch (Exception exc)
                    {
                        this.t.Abort();
                    }
                }
                complete = 40;
                for (int i = 0; i < threads.Count; i++)
                {
                    List<GraphLine> dummy = new List<GraphLine>();
                    dummy.AddRange(threads[i].GetVal());
                    dummy.Add(val[i]);
                    values.Add(dummy);
                    if (IsRoot)
                        Gr.PercentDone = GetPercentage(threads);
                }
                complete = 80;
                if (values.Count != 0)
                    val = FindShortest(values, PairsDistances, Pairs);
                if (IsRoot)
                {
                    Gr.PercentDone = 80;
                }
                complete = 100;
            }

            private int GetPercentage(List<PerfectMatchingThread> threads)
            {
                double total = 0;
                foreach (PerfectMatchingThread thr in threads)
                {
                    total += thr.complete;
                }
                return (int)((total / threads.Count)* 0.8);
            }

            private List<GraphLine> FindShortest(List<List<GraphLine>> values, List<double> PairsDistances, List<GraphLine> Pairs)
            {
                double minDist = Double.MaxValue;
                double distance;
                List<GraphLine> ret = null;
                foreach (List<GraphLine> list in values)
                {
                    distance = 0;
                    foreach (GraphLine line in list)
                    {
                        for (int i = 0; i < Pairs.Count; i++)
                        {
                            if (Pairs[i].HasSamePoints(line))
                            {
                                distance += PairsDistances[i];
                                break;
                            }
                        }
                    }
                    if (distance < minDist)
                    {
                        minDist = distance;
                        ret = list;
                    }
                }
                return ret;
            }

            public List<GraphLine> GetVal()
            {
                if (t.ThreadState == ThreadState.Unstarted)
                {
                    t.Start();
                    Gr.threadList.Add(t);
                }
                t.Join();
                return val;
            }

            private double GetLength()
            {
                double retVal = 0;
                foreach (GraphLine ln in val)
                {
                    for (int i = 0; i < Pairs.Count; i++)
                    {
                        if (ln.HasSamePoints(Pairs[i]) || ln == Pairs[i])
                        {
                            retVal += PairsDistances[i];
                        }
                    }
                }
                return retVal;
            }
        }

        public class GraphPointComparer : IComparer<GraphPoint>
        {
            public int Compare(GraphPoint x, GraphPoint y)
            {
                if (x.distance == y.distance)
                    return 0;
                if (x.distance < y.distance)
                    return -1;
                return 1;
            }
        }

        public class GraphLineComparer : IComparer<GraphLine>
        {
            public GraphLineComparer(GraphPoint st, GraphPoint en, List<GraphLine> Path)
            {
                start = st;
                end = en;
                path = Path;
            }
            private GraphPoint start;
            private GraphPoint end;
            private List<GraphLine> path;
            private int cnt = 0;
            public int Compare(GraphLine x, GraphLine y)
            {
                if (x.properties.IsRequired && !y.properties.IsRequired)
                    return -1;

                if (!x.properties.IsRequired && y.properties.IsRequired)
                    return 1;
                cnt++;
                bool contX = false;
                bool contY = false;
                foreach (GraphLine ln in path)
                {
                    if (ln == x)
                        contX = true;
                    if (ln == y)
                        contY = true;
                    if (contX && contY)
                        break;
                }
                if (contX && !contY)
                    return 1;
                if (contY && !contX)
                    return -1;

                if (x.HasGraphPoint(end))
                    return 1;
                if (y.HasGraphPoint(end))
                    return -1;
                double Xdist, Ydist;
                if (x.a.distance > x.b.distance)
                {
                    Xdist = x.b.distance;
                }
                else Xdist = x.a.distance;

                if (y.a.distance > y.b.distance)
                {
                    Ydist = y.b.distance;
                }
                else Ydist = y.a.distance;

                if (Xdist == Ydist)
                    return 0;
                if (Xdist < Ydist && Xdist != 0)
                    return -1;
                return 1;
            }
        }

        #endregion

        #region getters

        private int FindPoint(GraphPoint pt)
        {
            for (int i = 0; i < GraphPoints.Count; i++)
            {
                if (GraphPoints[i].point.X == pt.point.X && GraphPoints[i].point.Y == pt.point.Y)
                    return i;
            }
            return -1;
        }

        private int FindLine(GraphPoint a, GraphPoint b)
        {
            for (int i = 0; i < GraphLines.Count; i++)
            {
                if (GraphLines[i].a.CompareTo(a) && GraphLines[i].b.CompareTo(b)) return i;
                if (GraphLines[i].a.CompareTo(b) && GraphLines[i].b.CompareTo(a)) return i;
            }
            return -1;
        }

        public GraphLine GetLine(Point pt){
            foreach (GraphLine l in GraphLines)
            {
                if (l.IsAtTheLine(pt).X != -1)
                {
                    return l;
                }
            }
            return null;
        }

        #endregion

        #region modifiers

        public void AddLine(GraphPoint A, GraphPoint B,  LineProperties props = null)
        {
            if (A.point.X == B.point.X && A.point.Y == B.point.Y)
                return;
            int indexA = FindPoint(A);
            int indexB = FindPoint(B);
            if (indexA != -1 && indexB != -1)
            {
                if (FindLine(A, B) == -1)
                {
                    GraphPoints[indexA].wayCount++;
                    GraphPoints[indexB].wayCount++;
                    GraphLines.Add(new GraphLine(GraphPoints[indexA], GraphPoints[indexB], props));
                }
            }
            else if (indexA == -1 && indexB == -1)
            {
                GraphPoints.Add(A);
                GraphPoints.Add(B);
                A.wayCount++;
                B.wayCount++;
                GraphLines.Add(new GraphLine(GraphPoints[GraphPoints.Count - 2], GraphPoints[GraphPoints.Count - 1], props));
            }
            else if (indexA == -1)
            {
                GraphPoints.Add(A);
                A.wayCount++;
                B.wayCount++;
                GraphLines.Add(new GraphLine(GraphPoints[GraphPoints.Count - 1], GraphPoints[indexB], props));
            }
            else if (indexB == -1)
            {
                GraphPoints.Add(B);
                A.wayCount++;
                B.wayCount++;
                GraphLines.Add(new GraphLine(GraphPoints[indexA], GraphPoints[GraphPoints.Count - 1],props));
            }
        }

        public void Clear()
        {
            GraphLines.Clear();
            GraphPoints.Clear();
            start = null;
            end = null;
        }

        public void DeleteLine(GraphLine dummy)
        {
            GraphLines.Remove(dummy);
            dummy.a.wayCount--;
            dummy.b.wayCount--;
            if (dummy.a.wayCount == 0)
            {
                if (dummy.a == start)
                    start = null;
                if (dummy.a == end)
                    end = null;
                GraphPoints.Remove(dummy.a);
            }
            if (dummy.b.wayCount == 0)
            {
                if (dummy.b == start)
                    start = null; 
                if (dummy.b == end)
                    end = null;
                GraphPoints.Remove(dummy.b);
            }
            return;
        }

        public void DeletePoint(GraphPoint pt)
        {
            if (pt == end)
                end = null;
            if (pt == start)
                start = null;
            GraphPoints.Remove(pt);
            for (int i = 0; i < GraphLines.Count; i++)
            {
                if (GraphLines[i].a == pt || GraphLines[i].b == pt)
                {
                    DeleteLine(GraphLines[i]);
                    i--;
                }
            }
        }

        public void RebuildPointers(Size WindowSize) 
        {
            int checkWayCount = 0;
            foreach (GraphLine ln in GraphLines)
            {
                ln.Validate(WindowSize);
                checkWayCount = 0;
                foreach (GraphPoint pt in GraphPoints)
                {
                    if (ln.a.CompareTo(pt)) checkWayCount++;
                    if (ln.b.CompareTo(pt)) checkWayCount++;
                }
                if (checkWayCount != 2)
                    throw new FormatException();
            }

            foreach (GraphPoint pt in GraphPoints)
            {
                checkWayCount = 0;
                foreach (GraphLine line in GraphLines)
                {
                    if (line.a.CompareTo(pt))
                    {
                        line.a = pt;
                        checkWayCount++;
                    }
                    if (line.b.CompareTo(pt))
                    {
                        line.b = pt;
                        checkWayCount++;
                    }
                }
                if (checkWayCount != pt.wayCount)
                    throw new FormatException();
            }
            bool st = false, en = false;
            if (start == null) st = true;
            if (end == null) en = true;
            foreach (GraphLine line in GraphLines)
            {
                if(!st)
                    if (line.a.CompareTo(start))
                    {
                        start = line.a;
                        st = true;
                    }
                    else if (line.b.CompareTo(start))
                    {
                        start = line.b;
                        st = true;
                    }
                if (!en)
                    if (line.a.CompareTo(end))
                    {
                        end = line.a;
                        en = true;
                    }
                    else if (line.b.CompareTo(end))
                    {
                        end = line.b;
                        en = true;
                    }
                if (st && en)
                    break;
            }
        }

        #endregion

        #region walkthrough functions

        public void Abort()
        {
            aborted = true;
            try
            {
                if (threadList.Count != 0)
                {
                    if (threadList[0].IsAlive)
                    {

                        threadList[0].Abort();
                    }
                    threadList.RemoveAt(0);
                }
            }
            catch (Exception exc)
            {
            }
        }

        public int GetOddPointsCount()
        {
            int ret = 0;
            foreach (GraphPoint p in GraphPoints)
            {
                if (p.distance != Double.MaxValue && p.wayCount % 2 == 1)
                {
                    ret++;
                }
            }
            return ret;
        }

        public void PrepareForWalkthrough()
        {
            int count;
            foreach (GraphLine line in GraphLines)
            {
                line.WalkedCapacity = 1;
                line.WalkedTimes = 0;
                count = 1;
                if (line.neighboringLines == null)
                {
                    line.neighboringLines = new List<GraphLine>();
                }
                else
                {
                    line.neighboringLines.Clear();
                }
                foreach (GraphLine line2 in GraphLines)
                {
                    if (line.a.wayCount + line.b.wayCount == count + 1)
                        break;
                    if ((line.a == line2.a || line.a == line2.b || line.b == line2.b || line.b == line2.a) && line != line2)
                    {
                        line.neighboringLines.Add(line2);
                        count++;
                    }
                }
            }
        }

        public bool ShortestWay( GraphPoint a, GraphPoint b)
        {
             if (a == null || b == null)
            {
                a = start;
                b = end;
            }
            bool ret = false;
            if (a == b)
                ret = true;
            foreach (GraphPoint pt in GraphPoints)
            {
                pt.distance = Double.MaxValue;
                pt.opened = true;
            }
            a.distance = 0;
            a.opened = false;
            GraphPoint second = null;
            List<GraphPoint> ToVisit = new List<GraphPoint>();

            ToVisit.Add(a);
            while (ToVisit.Count != 0)
            {
                foreach (GraphLine line in GraphLines)
                {
                    second = line.GetSecondPoint(ToVisit[0]);
                    if (second != null)
                    {
                        if (second.opened)
                        {
                            if(line.Difficulty(ToVisit[0])<= 0 ){
                                line.Difficulty(ToVisit[0]);
                            }
                            if (second.distance > line.Difficulty(ToVisit[0]) + ToVisit[0].distance)
                            {
                                second.distance = line.Difficulty(ToVisit[0]) + ToVisit[0].distance;
                                ToVisit.Add(second);
                            }
                        }
                    }
                    if (second == b || ToVisit[0] == b)
                        ret = true;
                }
                ToVisit[0].opened = false;
                ToVisit.RemoveAt(0);
            }
            return ret;
        }

        private List<GraphLine> DijkstraLine(GraphPoint from, GraphPoint to, bool usingDifficulty, bool realWalk = true)
        {
            //vpodstate Dijkstra
            List<GraphLine> retVal = new List<GraphLine>();

            List<GraphLine> helpList = new List<GraphLine>();
            foreach (GraphLine l in WalkThroughGraphLines)
            {
                helpList.Add(l);
            }
            if (from == to)
                return retVal;
            foreach (GraphPoint pt in WalkThroughGraphPoints)
            {
                pt.distance = Double.MaxValue;
                pt.opened = true;
            }
            from.distance = 0;
            from.opened = false;
            GraphPoint second = null;
            GraphLine visited = null;
            List<GraphPoint> ToVisit = new List<GraphPoint>();
            ToVisit.Add(from);
            double len;
            while (ToVisit.Count != 0)
            {
                foreach (GraphLine line in helpList)
                {
                    second = line.GetSecondPoint(ToVisit[0]);
                    if (second != null)
                    {
                        if (second.opened)
                        {
                            if (usingDifficulty)
                            {
                                len = line.Difficulty(ToVisit[0]);
                            }
                            else
                            {
                                len = line.Length();
                            }
                            if (second.distance > len + ToVisit[0].distance)
                            {
                                second.distance = len + ToVisit[0].distance;
                                if (second != to)
                                    ToVisit.Add(second);
                                visited = line;
                            }
                        }
                    }
                }
                helpList.Remove(visited);
                if (ToVisit.Count == 0)
                    break;
                ToVisit[0].opened = false;
                ToVisit.RemoveAt(0);
            }
            GraphPoint current = to;
            GraphLine next = null;
            GraphPoint nextPt = null;
            double min;
            List<GraphLine> notExplored = new List<GraphLine>();
            foreach (GraphLine l in WalkThroughGraphLines)
            {
                notExplored.Add(l);
            }
            while (current != from)
            {
                min = current.distance;
                foreach (GraphLine l in notExplored)
                {

                    second = l.GetSecondPoint(current);
                    if (second != null)
                    {
                        if (usingDifficulty)
                        {
                            len = l.Difficulty(second);
                        }
                        else
                        {
                            len = l.Length();
                        }
                        if (second.distance + len == min)
                        {
                            next = l;
                            min = second.distance;
                            nextPt = second;
                        }
                    }
                }
                retVal.Add(next);
                if(realWalk)
                    next.WalkedTimes++;
                notExplored.Remove(next);
                current = nextPt;
            }
            retVal.Reverse();
            return retVal;
        }

        private void makeWalkGraph()
        {
            WalkThroughGraphLines = new List<GraphLine>();
            WalkThroughGraphPoints = new List<GraphPoint>();
            WalkThroughGraphLinesBanlist = new List<GraphLine>();
            foreach (GraphPoint p in GraphPoints)
            {
                if (p.distance != Double.MaxValue)
                {
                    WalkThroughGraphPoints.Add(p);
                    p.Enumerate(-1);
                }
            }
            WalkThroughGraphPoints.Sort(new GraphPointComparer());
            foreach (GraphLine l in GraphLines)
            {
                if (l.a.distance != Double.MaxValue || l.b.distance != Double.MaxValue)
                    WalkThroughGraphLines.Add(l);
            }
            List<GraphLine> Deposit;
            List<GraphLine> Deposit2 = new List<GraphLine>();
            if (start == end && start.wayCount > 2)
                Deposit = GetEndPoints();
            else
                Deposit = DijkstraLine(start, end, false, false);
            WalkThroughGraphLines.Sort(new GraphLineComparer(start, end, Deposit));
            Deposit.Clear();
            for (int i = 0; i < WalkThroughGraphLines.Count; i++)
            {
                if ((WalkThroughGraphLines[i].a.wayCount == 1 || WalkThroughGraphLines[i].b.wayCount == 1) && !WalkThroughGraphLines[i].HasGraphPoint(end))
                {
                    Deposit2.Add(WalkThroughGraphLines[i]);
                    WalkThroughGraphLines.RemoveAt(i);
                }
            }
            Deposit2.Sort(new GraphLineComparer(start, end, Deposit));
            WalkThroughGraphLines.InsertRange(0, Deposit2);
        }

        private List<GraphLine> GetEndPoints()
        {
            List<GraphLine> ln = new List<GraphLine>();
            foreach (GraphLine line in WalkThroughGraphLines)
                if (line.a.wayCount == 1 || line.b.wayCount == 1 && !ln.Contains(line))
                    ln.Add(line);
            return ln;
        }

        public void Walkthrough()
        {
            aborted = false;
            PercentDone = 0;
            makeWalkGraph();
            PercentDone = 10;
            if (EulerPathExists())
                output = MakeEulerPath(WalkThroughGraphLines);
            else
                output = MakeEulerPath(ConstructEulerianGraph());
            PercentDone = 90;
            MinimizePath(ref output);
            PercentDone = 100;
        }

        private void MinimizePath(ref List<GraphLine> euler)
        {

            List<GraphLine> requiredLines = new List<GraphLine>();
            foreach (GraphLine ln in WalkThroughGraphLines)
                if (ln.properties.IsRequired && !requiredLines.Contains(ln))
                    requiredLines.Add(ln);

            int i;
            if (requiredLines.Count == 0)
                euler.Clear();
            for (i = 0; i < euler.Count; i++)
            {
                
                if(requiredLines.Contains(euler[i]))
                    requiredLines.Remove(euler[i]);
                if (requiredLines.Count == 0)
                {
                    euler = euler.GetRange(0, i + 1);
                    break;
                }
            }
            euler = AssureRightCycleDirection(euler);
            euler = RemoveUnnecessaryNonRequiredLines(euler);


            GraphPoint lastPoint = GetLastPoint(euler);


            if (lastPoint == null)
                lastPoint = start;
            if (lastPoint != end)
                euler.AddRange(DijkstraLine(lastPoint, end, true, false));
        }

        private List<GraphLine> RemoveUnnecessaryNonRequiredLines(List<GraphLine> euler)
        {
            List<GraphLine> retVal = new List<GraphLine>();
            GraphPoint first = null, last = null;
            first = start;
            int j = 0;
            for (int i = 0; i < euler.Count; i++)
            {
                if (euler[i].properties.IsRequired)
                {
                    retVal.Add(euler[i]);
                    first = euler[i].GetSecondPoint(first);
                }
                else
                {
                    last = first;
                    for (j = i; j < euler.Count; j++)
                    {
                        if (!euler[j].properties.IsRequired)
                        {
                            last = euler[j].GetSecondPoint(last);
                        }
                        else
                        {
                            break;
                        }
                    }
                    retVal.AddRange(DijkstraLine(first, last, true));
                    first = GetLastPoint(retVal);
                    i = j-1;
                }
                
            }
            return retVal;
        }

        private GraphPoint GetLastPoint(List<GraphLine> path)
        {
            if (path.Count == 0)
                return null;
            if (path.Count == 1)
            {
                return path[0].GetSecondPoint(start);
            }
            if (path[path.Count - 1].HasGraphPoint(path[path.Count - 2].a) && path[path.Count - 1].HasGraphPoint(path[path.Count - 2].b))
            {
                GraphPoint pt = start;
                foreach (GraphLine ln in path)
                {
                    pt = ln.GetSecondPoint(pt);
                }
                return pt;
            }
            if (path[path.Count - 1].HasGraphPoint(path[path.Count - 2].a))
            {
                return path[path.Count - 1].GetSecondPoint(path[path.Count - 2].a);
            }
            else
            {
                return path[path.Count - 1].GetSecondPoint(path[path.Count - 2].b);
            }
        }

        private GraphPoint GetFirstPoint(List<GraphLine> path)
        {
            if (path.Count == 0)
                return null;
            if (path.Count == 1)
                return path[0].GetSecondPoint(end);
            if (path[0].HasGraphPoint(path[1].a) && path[0].HasGraphPoint(path[1].b))
            {
                return start;
            }
            if (path[0].HasGraphPoint(path[1].a))
            {
                return path[0].GetSecondPoint(path[1].a);
            }
            else
            {
                return path[0].GetSecondPoint(path[1].b);
            }
        }

        public List<GraphPoint> GetGraphPointsFromGraphLineList(List<GraphLine> path)
        {
            List<GraphPoint> retVal = new List<GraphPoint>();
            GraphPoint pt = start;
            foreach (GraphLine ln in path)
            {
                if(pt != null)
                    retVal.Add(pt);
                pt = ln.GetSecondPoint(pt);
            }
            if (pt != null)
            retVal.Add(pt);
            return retVal;
        }

        private bool ShouldReverse(List<GraphPoint> points, List<GraphLine> path)
        {
            List<GraphPoint> pointCycle = new List<GraphPoint>();
            pointCycle.AddRange(points);
            for (int i = 1; i < pointCycle.Count - 1; i++)
            {
                for (int j = pointCycle.Count - 2; j > i; j--)
                {
                    if (pointCycle[i] == pointCycle[j])
                    {
                        pointCycle.RemoveRange(i+1, j - i);
                        i = 0;
                        break;
                    }
                }
            }
            List<GraphLine> lineCycle = new List<GraphLine>();
            List<GraphLine> fakeCycle = new List<GraphLine>();

            for (int i = 1; i < pointCycle.Count; i++)
                fakeCycle.Add(new GraphLine(pointCycle[i - 1], pointCycle[i]));

            foreach (GraphLine fake in fakeCycle)
            {
                foreach (GraphLine real in path)
                {
                    if (real.HasSamePoints(fake))
                    {
                        lineCycle.Add(real);
                        break;
                    }
                }
            }
            double dist = 0, revDist = 0;
            GraphPoint pt = GetFirstPoint(lineCycle);
            foreach (GraphLine ln in lineCycle)
            {
                dist += ln.Difficulty(pt);
                pt = ln.GetSecondPoint(pt);
            }
            lineCycle.Reverse();
            pt = GetFirstPoint(lineCycle);
            foreach (GraphLine ln in lineCycle)
            {
                revDist += ln.Difficulty(pt);
                pt = ln.GetSecondPoint(pt);
            }

            if (revDist < dist)
                return true;
            return false;
        }

        private List<GraphLine> AssureRightCycleDirection(List<GraphLine> path)
        {
            List<GraphPoint> points = GetGraphPointsFromGraphLineList(path);
            for (int i = 0; i < points.Count; i++)
            {
                for (int j = points.Count - 1; j > i; j--)
                {
                    if (points[i] == points[j])
                    {
                        if (ShouldReverse(points.GetRange(i, j + 1 -i), path))
                        {
                            points.Reverse(i, j + 1 - i);
                        }
                    }
                }
            }

            List<GraphLine> fakes = new List<GraphLine>();
            List<GraphLine> reals = new List<GraphLine>();
            for (int i = 1; i < points.Count; i++)
                fakes.Add(new GraphLine(points[i-1], points[i]));

            foreach (GraphLine fake in fakes)
            {
                foreach (GraphLine real in path)
                {
                    if (real.HasSamePoints(fake))
                    {
                        reals.Add(real);
                        break;
                    }
                }
            }

            return reals;
        }

        #endregion

        #region euler path definitions

        public List<GraphPoint> FindOddPoints()
        {
            List<GraphPoint> retVal = new List<GraphPoint>();
            foreach (GraphPoint pt in WalkThroughGraphPoints)
            {
                if (pt.wayCount % 2 == 1)
                    retVal.Add(pt);
            }
            return retVal;
        }

        private bool EulerPathExists()
        {
            int t = start.wayCount + end.wayCount;
            if (t % 2 != 0)
                return false;
            foreach (GraphPoint pt in WalkThroughGraphPoints)
            {
                if (pt != start && pt != end)
                    if (pt.wayCount % 2 != 0)
                        return false;
            }
            return true;
        }

        private List<GraphLine> MakeEulerPath(List<GraphLine> source)
        {
            List<GraphLine> retVal = new List<GraphLine>();
            S = new Stack<GraphPoint>();
            S2 = new Stack<GraphLine>();
            GraphPoint v = start;
            List<GraphLine> graph = new List<GraphLine>();
            graph.AddRange(source);
            int rounds = 0;
            while (MakeEulerPathSubCircuit(ref v, ref graph) == v && S.Count != 0)
            {
                rounds++;
                v = S.Pop();
                retVal.Add(S2.Pop());
            }
            
            retVal.Reverse();
            return retVal;
            
        }

        private GraphPoint MakeEulerPathSubCircuit(ref GraphPoint current, ref List<GraphLine> graph)
        {
            GraphPoint second = null;
            while (true)
            {
                List<GraphPoint> points = PointNeighbours(current, graph);
                if (points.Count == 0) break;
                second = points[0];
                S.Push(current);
                for(int i = 0; i < graph.Count; i++)
                    if (graph[i].HasGraphPoint(current) && graph[i].HasGraphPoint(second))
                    {
                        S2.Push(graph[i]);
                        graph[i].WalkedTimes++;
                        if(graph[i].WalkedTimes >= graph[i].WalkedCapacity)
                            graph.RemoveAt(i);
                        break;
                    }
                current = second;
            }
            return current;
        }

        private List<GraphLine> perfectMatching(List<GraphPoint> odds, List<GraphLine> pairs, List<double> pairsDistances)
        {
            if (odds.Count == 0 || pairs.Count == 0 || pairsDistances.Count == 0)
                return new List<GraphLine>();
            List<List<GraphLine>> values = new List<List<GraphLine>>();
            List<GraphPoint> oddsDown = new List<GraphPoint>();
            List<GraphLine> val = new List<GraphLine>();
            GraphLine current = null;
            for (int j = 1; j < odds.Count; j++)
            {
                current = new GraphLine(odds[0], odds[j]);
                oddsDown.Clear();
                foreach (GraphPoint pt in odds)
                    if (pt != odds[0] && pt != odds[j])
                        oddsDown.Add(pt);
                val = perfectMatching(oddsDown, pairs, pairsDistances);
                    val.Add(current);
                    values.Add(val);
            }
            return FindShortest(values, pairsDistances, pairs);
        }
       
        private List<GraphLine> FindShortest(List<List<GraphLine>> values, List<double> PairsDistances, List<GraphLine> Pairs)
        {
            double minDist = Double.MaxValue;
            double distance;
            List<GraphLine> ret = null;
            foreach (List<GraphLine> list in values)
            {
                distance = 0;
                foreach (GraphLine line in list)
                {
                    for (int i = 0; i < Pairs.Count; i++)
                    {
                        if (Pairs[i].HasSamePoints(line))
                        {
                            distance += PairsDistances[i];
                            break;
                        }
                    }
                }
                if (distance < minDist)
                {
                    minDist = distance;
                    ret = list;
                }
            }
            return ret;
        }

        private List<GraphLine> ConstructEulerianGraph()
        {
            threadList = new List<Thread>();
            List<GraphPoint> odds = FindOddPoints();
            List<List<GraphLine>> pairs = new List<List<GraphLine>>();
            List<GraphLine> retVal = new List<GraphLine>();
            retVal.AddRange(WalkThroughGraphLines);
            List<double> pairsDistances = new List<double>();
            for (int i = 0; i < odds.Count; i++)
                for (int j = i+1; j < odds.Count; j++)
                    if (i != j)
                    {
                        pairs.Add(DijkstraLine(odds[i], odds[j], false, false));
                        pairsDistances.Add(odds[j].distance);
                    }
            List<GraphLine> minimizedPairs = minimizePairs(pairs);
            PercentDone = 20;
            PerfectMatchingThread thr = new PerfectMatchingThread(odds, minimizedPairs, pairsDistances, this);
            List<GraphLine> perfectMatches = thr.GetVal();
            List<GraphLine> toDuplicate = new List<GraphLine>();
            foreach (GraphLine ln in perfectMatches)
            {
                toDuplicate.AddRange(DijkstraLine(ln.a, ln.b, false, false));
            }

            foreach (GraphLine ln in toDuplicate)
            {
                retVal.Add(ln);
            }

            return retVal;
        }

        private List<GraphLine> minimizePairs(List<List<GraphLine>> pairs)
        {
            List<GraphLine> retVal = new List<GraphLine>();
            GraphPoint first;
            GraphPoint last;
            foreach (List<GraphLine> list in pairs)
            {
                if (list.Count == 1)
                {
                    retVal.Add(list[0]);
                }
                else
                {
                    if (list[1].HasGraphPoint(list[0].a))
                    {
                        first = list[0].b;
                    }
                    else
                    {
                        first = list[0].a;
                    }
                    if (list[list.Count - 2].HasGraphPoint(list[list.Count - 1].a))
                    {
                        last = list[list.Count - 1].b;
                    }
                    else
                    {
                        last = list[list.Count - 1].a;
                    }
                    retVal.Add(new GraphLine(first, last));
                }
            }
            return retVal;
        }

        private List<GraphPoint> PointNeighbours(GraphPoint current, List<GraphLine> graph)
        {

            List<GraphPoint> retVal = new List<GraphPoint>();
            int cnt = 0;
            foreach (GraphLine ln in graph)
            {
                if (ln.HasGraphPoint(current))
                {
                    cnt++;
                    retVal.Add(ln.GetSecondPoint(current));
                }
                if (cnt == current.wayCount) break;
            }
            return retVal;
        }

        private bool CompareLists(List<GraphLine> first, List<GraphLine> second)
        {
            foreach (GraphLine l1 in first)
            {
                if (!second.Contains(l1))
                {
                    return false;//nonidentic
                }
            }
            return true;
        }

        #endregion

    }

}

